#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
  /*暴力枚举解法*/
  int subarraySum(vector<int> &nums, int k) {
    int n = nums.size();
    if (n == 1) {
      return nums[0] == k ? 1 : 0;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      int temp_sum = nums[i];
      int j = i + 1;
      while (j < n) {
        // 满足条件
        if (temp_sum == k) {
          res++;
        }
        // 右侧扩大窗口
        temp_sum += nums[j++];
      }
      if (temp_sum == k) {
        res++;
      }
    }
    return res;
  }
  /*前缀和+哈希表解法*/
  int subarraySum_(vector<int> &nums, int k) {
    int n = nums.size();
    // 存储前缀和以及其出现次数
    unordered_map<int, int> _map;
    int res = 0, pre = 0;
    for (int i = 0; i < n; i++) {
      pre += nums[i];
      if (pre == k)
        res++;
      auto iter = _map.find(pre - k);
      if (iter != _map.end()) {
        res += iter->second;
      }
      // 更新map中的数据
      if (_map.find(pre) != _map.end()) {
        _map[pre]++;
      } else {
        _map[pre] = 1;
      }
    }
    return res;
  }
};